{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Right Interval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRightInterval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找右区间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个区间数组 <code>intervals</code> ，其中&nbsp;<code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> ，且每个&nbsp;<code>start<sub>i</sub></code> 都 <strong>不同</strong> 。</p>\n",
    "\n",
    "<p>区间 <code>i</code> 的 <strong>右侧区间</strong> 可以记作区间 <code>j</code> ，并满足 <code>start<sub>j</sub></code><code>&nbsp;&gt;= end<sub>i</sub></code> ，且 <code>start<sub>j</sub></code> <strong>最小化 </strong>。注意 <code>i</code> 可能等于 <code>j</code> 。</p>\n",
    "\n",
    "<p>返回一个由每个区间 <code>i</code> 的 <strong>右侧区间</strong> 在&nbsp;<code>intervals</code> 中对应下标组成的数组。如果某个区间 <code>i</code> 不存在对应的 <strong>右侧区间</strong> ，则下标 <code>i</code> 处的值设为 <code>-1</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,2]]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>集合中只有一个区间，所以输出-1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[3,4],[2,3],[1,2]]\n",
    "<strong>输出：</strong>[-1,0,1]\n",
    "<strong>解释：</strong>对于 [3,4] ，没有满足条件的“右侧”区间。\n",
    "对于 [2,3] ，区间[3,4]具有最小的“右”起点;\n",
    "对于 [1,2] ，区间[2,3]具有最小的“右”起点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>intervals = [[1,4],[2,3],[3,4]]\n",
    "<strong>输出：</strong>[-1,2,-1]\n",
    "<strong>解释：</strong>对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。\n",
    "对于 [2,3] ，区间 [3,4] 有最小的“右”起点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;intervals.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>intervals[i].length == 2</code></li>\n",
    "\t<li><code>-10<sup>6</sup> &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li>每个间隔的起点都 <strong>不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-right-interval](https://leetcode.cn/problems/find-right-interval/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-right-interval](https://leetcode.cn/problems/find-right-interval/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2]]', '[[3,4],[2,3],[1,2]]', '[[1,4],[2,3],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        intervals_with_idx = [[start, idx] for idx, (start, end) in enumerate(intervals)]\n",
    "        intervals_with_idx.sort()\n",
    "        starts = [x[0] for x in intervals_with_idx]\n",
    "        res = [-1] * n\n",
    "\n",
    "        def leftBounder(target):\n",
    "            left, right = 0, n - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if starts[mid] >= target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        for i in range(n):\n",
    "            temp_start_idx = leftBounder(intervals[i][1])\n",
    "            if temp_start_idx < n:\n",
    "                res[i] = intervals_with_idx[temp_start_idx][1]\n",
    "        \n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        starts, ends = list(zip(*intervals))\n",
    "        starts = sorted(zip(starts, range(n)))\n",
    "        ends = sorted(zip(ends, range(n)))\n",
    "        ans = [-1] * n\n",
    "        j = 0\n",
    "        for i in range(n):\n",
    "            while j < n and ends[i][0] > starts[j][0]:\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                ans[ends[i][1]] = starts[j][1]\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        def searchSatrt(nums, left, right, target):\n",
    "            while left <= right:\n",
    "                mid = (right+left)//2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "\n",
    "        Dict = {}\n",
    "        for ind, (start, end) in enumerate(intervals):\n",
    "            Dict[start] = ind\n",
    "        Keys = sorted(Dict.keys())\n",
    "        rlist = []\n",
    "        n = len(Dict) - 1\n",
    "        for _, end in intervals:\n",
    "            ind = searchSatrt(Keys, 0, n, end)\n",
    "            if ind <= n:\n",
    "                k = Keys[ind]\n",
    "                rlist.append(Dict[k])\n",
    "            else:\n",
    "                rlist.append(-1)\n",
    "        return rlist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: list[list[int]]) -> list[int]:\n",
    "        n = len(intervals)\n",
    "        if n == 1:\n",
    "            return [-1]\n",
    "        for i in range(n):\n",
    "            intervals[i].append(i)\n",
    "        res = [0 for _ in range(n)]\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "\n",
    "        def bisearch(l, target):\n",
    "            n = len(l)\n",
    "            if n == 1:\n",
    "                if l[0][0] >= target:\n",
    "                    return l[0][2]\n",
    "                else:\n",
    "                    return -1\n",
    "            if n == 0:\n",
    "                return -1\n",
    "            mid = n // 2\n",
    "            if l[mid][0] == target:\n",
    "                return l[mid][2]\n",
    "            else:\n",
    "                if l[mid][0] < target:\n",
    "                    return bisearch(l[mid + 1:], target)\n",
    "                else:\n",
    "                    if l[mid - 1][0] < target:\n",
    "                        return l[mid][2]\n",
    "                    else:\n",
    "                        return bisearch(l[:mid], target)\n",
    "\n",
    "        for i in range(n):\n",
    "            res[intervals[i][2]] = bisearch(intervals, intervals[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, left, right, intervals, target):\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if intervals[mid][0] > target:\n",
    "                right = mid\n",
    "            elif intervals[mid][0] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        if left >= len(intervals) or intervals[left][0] < target:\n",
    "            return -1\n",
    "        return left\n",
    "\n",
    "\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "\n",
    "        dic = defaultdict()\n",
    "        for i in range(len(intervals)):\n",
    "            dic[intervals[i][0]] = i\n",
    "        intervals = sorted(intervals)\n",
    "        res = [-1] * len(intervals)\n",
    "        for i in range(len(intervals)):\n",
    "            target = intervals[i][1]\n",
    "            tmp = self.search(i, len(intervals) - 1, intervals, target)\n",
    "            res[dic[intervals[i][0]]] = dic[intervals[tmp][0]] if tmp != -1 else -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        if len(intervals)==1:\n",
    "            if intervals[0][0]==intervals[0][1]:\n",
    "                return [0]\n",
    "            return [-1]\n",
    "        n=len(intervals)\n",
    "        ans=[-1 for i in range(n)]\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            arr.append([i,intervals[i][0]])\n",
    "        arr.sort(key = lambda x: (x[1]))\n",
    "        for i in range(n):\n",
    "            x=intervals[arr[i][0]][1]\n",
    "            p=-1\n",
    "            for j in range(i,n):\n",
    "                if intervals[arr[j][0]][0]>=x:\n",
    "                    p=arr[j][0]\n",
    "                    break\n",
    "            ans[arr[i][0]]=p\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        s = sorted(range(n), key=lambda x: intervals[x][0])\n",
    "        ans = list()\n",
    "        l, r = intervals[s[0]][0], intervals[s[-1]][0]\n",
    "        for x, y in intervals:\n",
    "            if y < l or y > r:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                left, right = 0, n - 1\n",
    "                while left < right:\n",
    "                    mid = (left + right) >> 1\n",
    "                    if y > intervals[s[mid]][0]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid\n",
    "                ans.append(s[left])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        # res = [-1] * n\n",
    "        # dt = collections.defaultdict()\n",
    "        # for i, inter in enumerate(intervals):\n",
    "        #     dt[(inter[0] + 10 ** 6 ) * 10 + (inter[1] + 10 ** 6 )] = i\n",
    "\n",
    "        # sinter = sorted(intervals, key = lambda x : (x[1], x[0]))\n",
    "        # j = 1\n",
    "        # i = 0\n",
    "        # while i < n:\n",
    "        #     if j == n:\n",
    "        #         break\n",
    "        #     if sinter[i][1] > sinter[j][0]:\n",
    "        #         j += 1\n",
    "        #         continue\n",
    "        #     tmp = 10 * (sinter[i][0]+ 10 ** 6) + (sinter[i][1] + 10 ** 6)\n",
    "        #     ri = 10 * (sinter[j][0]+ 10 ** 6) + (sinter[j][1]+ 10 ** 6)\n",
    "        #     res[dt[tmp]] = dt[ri]\n",
    "        #     i += 1\n",
    "\n",
    "        # return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        start=[x[0] for x in intervals]\n",
    "        seq_start=sorted(start)  # 记录区间的左边，且排序\n",
    "        res=[]\n",
    "        for _,end in intervals:\n",
    "            if end>seq_start[-1]:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                idx=bisect.bisect_left(seq_start,end)\n",
    "                res.append(start.index(seq_start[idx]))\n",
    "        return res\n",
    "        ##\n",
    "\n",
    "        # start=[x[0] for x in intervals]\n",
    "        # seq_start=sorted(start)  # 记录区间的左边，且排序\n",
    "        # res=[]\n",
    "        # m=len(intervals)\n",
    "        # for _,k in intervals: \n",
    "        #     if k > seq_start[-1]:\n",
    "        #         res.append(-1)         \n",
    "        #     else:\n",
    "        #         j=0\n",
    "        #         while j<m:\n",
    "        #             if k <= seq_start[j]:\n",
    "        #                 res.append(start.index(seq_start[j]))\n",
    "        #                 break\n",
    "        #             j+=1               \n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, itvals: List[List[int]]) -> List[int]:\n",
    "        n = len(itvals)\n",
    "        idxs = [i for i in range(n)]\n",
    "        idxs.sort(key=lambda x: (itvals[x][0], itvals[x][1]))\n",
    "        ans = [-1] * (n)\n",
    "        for i in range(n):\n",
    "            nl, nr = itvals[idxs[i]]\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                if itvals[idxs[m]][0] < nr:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            if l < n:\n",
    "                ans[idxs[i]] = idxs[l]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        m = sorted([ (i[0], index) for index, i in enumerate(intervals) ])\n",
    "        res = [-1] * len(intervals)\n",
    "\n",
    "        for index, item in enumerate(intervals):\n",
    "            left, right = -1, len(m)\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if m[mid][0] < item[1]: left = mid\n",
    "                else: right = mid\n",
    "\n",
    "            if right != len(m):\n",
    "                res[index] = m[right][1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\r\n",
    "        n = len(intervals)\r\n",
    "\r\n",
    "        items = [intervals[i] + [i] for i in range(n)]\r\n",
    "        items.sort()\r\n",
    "        ans = [-1] * n\r\n",
    "        for i in range(n):\r\n",
    "            start, end, j = items[i]\r\n",
    "\r\n",
    "            left, right = i, n - 1\r\n",
    "            while left <= right:\r\n",
    "                mid = (left + right) // 2\r\n",
    "                if items[mid][0] >= end:\r\n",
    "                    ans[j] = items[mid][2]\r\n",
    "                    right = mid - 1\r\n",
    "                else:\r\n",
    "                    left = mid + 1\r\n",
    "        \r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "        n = len(intervals)\n",
    "        starts = [[intervals[i][0], i] for i in range(n)]\n",
    "        starts.sort()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            # left = -1\n",
    "            # right = n\n",
    "            # while left + 1 < right:\n",
    "            #     mid = (left + right) // 2\n",
    "            #     if starts[mid][0] >= intervals[i][1]:\n",
    "            #         right = mid\n",
    "            #     else:\n",
    "            #         left = mid\n",
    "            j =  bisect.bisect_left(starts, [intervals[i][1]])\n",
    "            if j > n-1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(starts[j][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        m = sorted([ (i[0], index) for index, i in enumerate(intervals) ])\n",
    "        mn = max(i[0] for i in intervals)\n",
    "        res = []\n",
    "\n",
    "        for item in intervals:\n",
    "            left, right = -1, len(m)\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if m[mid][0] < item[1]: left = mid\n",
    "                else: right = mid\n",
    "\n",
    "            if right == len(m):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(m[right][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n,stk=len(intervals),[];ans=[-1]*n\n",
    "        intervals=sorted([(intervals[i][0],intervals[i][1],i) for i in range(n)])\n",
    "        for i in intervals:\n",
    "            heapq.heappush(stk,(i[1],i[2]))\n",
    "            while(len(stk) and stk[0][0]<=i[0]):ans[stk[0][1]]=i[2];heapq.heappop(stk)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "        n = len(intervals)\n",
    "        starts = [[intervals[i][0], i] for i in range(n)]\n",
    "        starts.sort()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            # left = -1\n",
    "            # right = n\n",
    "            # while left + 1 < right:\n",
    "            #     mid = (left + right) // 2\n",
    "            #     if starts[mid][0] >= intervals[i][1]:\n",
    "            #         right = mid\n",
    "            #     else:\n",
    "            #         left = mid\n",
    "            j =  bisect.bisect_left(starts, [intervals[i][1]])\n",
    "            if j > n-1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(starts[j][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        records = [[j[0], i] for i, j in enumerate(intervals)]\n",
    "        records.sort()\n",
    "        ans = []\n",
    "        n = len(intervals)\n",
    "        for x, y in intervals:\n",
    "            temp = [y, 0]\n",
    "            k = -1\n",
    "            m = bisect.bisect_left(records, temp)\n",
    "            if m != n:\n",
    "                k = records[m][1]\n",
    "            ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        number=len(intervals)\n",
    "        left=list(range(number))\n",
    "        left.sort(key=lambda x :intervals[x][0])\n",
    "        lefter=[intervals[x][0] for x in left]\n",
    "        ans=[-1]*number\n",
    "        for i in range(number):\n",
    "            jer=bisect.bisect_left(lefter,intervals[i][1])\n",
    "            if jer<number:\n",
    "                ans[i]=left[jer]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        starts = [[intervals[i][0], i] for i in range(n)]\n",
    "        starts.sort()\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            left = -1\n",
    "            right = n\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if starts[mid][0] >= intervals[i][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "\n",
    "            if right > n-1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(starts[right][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        ans = [0] * n\n",
    "        sorted_intervals = sorted(enumerate(intervals), key=lambda x: x[1])\n",
    "        for i, interval in enumerate(sorted_intervals):\n",
    "            left = -1\n",
    "            right = n \n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if sorted_intervals[mid][1][0] >= interval[1][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            if right == n:\n",
    "                ans[interval[0]] = -1\n",
    "            else:\n",
    "                ans[interval[0]] = sorted_intervals[right][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "        n = len(intervals)\n",
    "        \n",
    "\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda x: intervals[x][0])\n",
    "        left = [intervals[x][0] for x in ind]\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            j = bisect.bisect_left(left, intervals[i][1])\n",
    "            if j < n:\n",
    "                ans[i] = ind[j]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        m = sorted([ (i[0], index) for index, i in enumerate(intervals) ])\n",
    "        res = []\n",
    "\n",
    "        for item in intervals:\n",
    "            left, right = -1, len(m)\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if m[mid][0] < item[1]: left = mid\n",
    "                else: right = mid\n",
    "\n",
    "            if right == len(m):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(m[right][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        return [lt[idx][1] if (idx := bisect_left(lt, b, key=lambda x:x[0])) < len(lt) else -1 for _, b in intervals] if (lt := sorted([[inter[0], i] for i, inter in enumerate(intervals)])) else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        # 让索引按照对应的左端点排序\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda x: intervals[x][0])\n",
    "        left = [intervals[x][0] for x in ind]\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            # 二分查找最近的右侧区间\n",
    "            j = bisect.bisect_left(left, intervals[i][1])\n",
    "            if j < n:\n",
    "                ans[i] = ind[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        interList = list(enumerate(intervals))\n",
    "        interList.sort(key = lambda x:(x[1][0],x[1][1]))\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            x1,x2 = interList[i]\n",
    "            for k in range(i,n):\n",
    "                y1,y2 = interList[k]\n",
    "                if x2[1] <= y2[0]:\n",
    "                    ans[x1] = y1\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        idx = list(range(n))\n",
    "        idx.sort(key=lambda x: intervals[x][0])\n",
    "\n",
    "        left = [intervals[x][0] for x in idx]\n",
    "        ans = [-1]*n\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            j = bisect.bisect_left(left,intervals[i][1])\n",
    "\n",
    "            if j < n:\n",
    "                ans[i] = idx[j]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        mapping = {}\n",
    "        l_list = []\n",
    "        for i in range(len(intervals)):\n",
    "            mapping[intervals[i][0]] = i \n",
    "            l_list.append(intervals[i][0])\n",
    "        \n",
    "        l_list.sort()\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for _, r in intervals:\n",
    "            temp = bisect_left(l_list, r)\n",
    "            if temp == len(intervals):\n",
    "                ret.append(-1)\n",
    "            else:\n",
    "                ret.append(mapping[l_list[temp]])\n",
    "        return ret\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        # 让索引按照对应的左端点排序\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda x: intervals[x][0])\n",
    "        left = [intervals[x][0] for x in ind]\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            # 二分查找最近的右侧区间\n",
    "            j = bisect.bisect_left(left, intervals[i][1])\n",
    "            if j < n:\n",
    "                ans[i] = ind[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(intervals)\n",
    "        if (lt := sorted([[inter[0], i] for i, inter in enumerate(intervals)])):\n",
    "            for _, b in intervals:\n",
    "                if (idx := bisect_left(lt, b, key=lambda x:x[0])) < n:\n",
    "                    res.append(lt[idx][1])\n",
    "                else:\n",
    "                    res.append(-1)\n",
    "        else:\n",
    "            res = []\n",
    "        return res\n",
    "\n",
    "# 作者：Benhao\n",
    "# 链接：https://leetcode.cn/problems/find-right-interval/solutions/1505938/pythonjavajavascriptgo-by-himymben-p8xb/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        temp=dict()\n",
    "        for i,item in enumerate(intervals):\n",
    "            temp[(item[0],item[1])]=i\n",
    "        intervals.sort()\n",
    "        ret=[None]*len(intervals)\n",
    "\n",
    "        for i in range(len(intervals)):\n",
    "            endi=intervals[i][1]\n",
    "            judge=0\n",
    "            for j in range(i,len(intervals)):\n",
    "                if intervals[j][0]>=endi:\n",
    "                    ret[temp[tuple(intervals[i])]]=j\n",
    "                    judge=1\n",
    "                    break\n",
    "\n",
    "            if judge==0:\n",
    "                ret[temp[tuple(intervals[i])]]=-1\n",
    "        for i in range(len(ret)):\n",
    "            if ret[i]!=-1:\n",
    "                ret[i]=temp[tuple(intervals[ret[i]])]\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        tmp = []\n",
    "        for i, (x, y) in enumerate(intervals):\n",
    "            d[x] = i\n",
    "            tmp.append(x)\n",
    "        tmp.sort()\n",
    "        n = len(intervals)\n",
    "        ret = [-1] * n\n",
    "        for i, (x, y) in enumerate(intervals):\n",
    "            idx = bisect_left(tmp, y)\n",
    "            if idx < n:\n",
    "                ret[i] = d[tmp[idx]]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        dic={}\n",
    "        for i,x in enumerate(intervals):\n",
    "            #建立下标x与i之间的映射\n",
    "            dic[x[0]]=i\n",
    "        #保存每个interval的start\n",
    "        start=[x[0] for x in intervals]\n",
    "        start.sort()#从小到大排序\n",
    "        res=[]\n",
    "        #遍历interval，获取每个end\n",
    "        #在已经排序的start里面插入end通过二分法，找到大于等于这个end的最小值\n",
    "        for _ ,end in intervals:\n",
    "            index=bisect.bisect_left(start,end)\n",
    "            #最后一个元素，插入-1\n",
    "            if index==len(start):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                #映射找到下标\n",
    "                res.append(dic[start[index]])\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        ans = [0] * n\n",
    "        sorted_intervals = sorted(enumerate(intervals), key=lambda x: x[1])\n",
    "        for i, interval in enumerate(sorted_intervals):\n",
    "            left = -1\n",
    "            right = n \n",
    "            while left + 1 < right:\n",
    "                print(i, left, right)\n",
    "                mid = (left + right) // 2\n",
    "                if sorted_intervals[mid][1][0] >= interval[1][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            if right == n:\n",
    "                ans[interval[0]] = -1\n",
    "            else:\n",
    "                ans[interval[0]] = sorted_intervals[right][0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        starts = [[intervals[i][0], i] for i in range(n)]\n",
    "        starts.sort()\n",
    "        print(starts)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            left = -1\n",
    "            right = n\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if starts[mid][0] >= intervals[i][1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "\n",
    "            if right > n-1:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(starts[right][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # 对区间开始节点按照升序做数组排列\n",
    "        dic = {}\n",
    "        start = []\n",
    "        for i, t in enumerate(intervals):\n",
    "            start.append(t[0])\n",
    "            dic[t[0]] = i\n",
    "        start.sort()\n",
    "        ret = []\n",
    "        for s, e in intervals:\n",
    "            index = bisect.bisect_left(start, e)\n",
    "            if index < len(start):\n",
    "                ret.append(dic[start[index]])\n",
    "            else:\n",
    "                ret.append(-1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        m = sorted([ (i[0], index) for index, i in enumerate(intervals) ])\n",
    "        mn = max(i[0] for i in intervals)\n",
    "        res = []\n",
    "\n",
    "        print(m)\n",
    "\n",
    "        for item in intervals:\n",
    "            left = -1\n",
    "            right = len(m)\n",
    "            while left + 1 < right:\n",
    "                mid = left + right >> 1\n",
    "                if m[mid][0] < item[1]:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            # print(item, right)\n",
    "            if right == len(m):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(m[right][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        starts = {}\n",
    "        for i in range(len(intervals)):\n",
    "            starts[intervals[i][0]] = i\n",
    "\n",
    "        sorted_starts = sorted(starts.keys())\n",
    "\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            index = bisect.bisect_left(sorted_starts, interval[1])\n",
    "            if index == len(intervals):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(starts[sorted_starts[index]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        l = SortedList(key=lambda x: x[0])\n",
    "        for i, interval in enumerate(intervals):\n",
    "            l.add((interval[0], i))\n",
    "        inds = [i[1] for i in l]\n",
    "        starts = [i[0] for i in l]\n",
    "\n",
    "        res = []\n",
    "        for interval in intervals:\n",
    "            end = interval[1]\n",
    "            r = bisect.bisect_left(starts, end, 0)\n",
    "            if r == len(inds):\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                res.append(inds[r])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "\n",
    "        res = [-1 for _ in range(len(intervals))]\n",
    "        memo_dict = {}\n",
    "        for idx, i in enumerate(intervals):\n",
    "            memo_dict[i[0]] = idx\n",
    "            \n",
    "        search_list = [i[0] for i in intervals]\n",
    "        search_list = sorted(search_list)\n",
    "        # 二分法\n",
    "        def search(index, end):\n",
    "            left = 0\n",
    "            right = len(search_list) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left)//2\n",
    "                # 正好相同，就不用再搜索了，res填值\n",
    "                if search_list[mid] == end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    break\n",
    "                # 大于的话就往左移动\n",
    "                elif search_list[mid] > end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    right = mid - 1\n",
    "                # 小于往右移动\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "        \n",
    "\n",
    "        for index, i in enumerate(intervals):\n",
    "            search(index, i[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        #解题思路：\n",
    "        #梳理：对每个区间[start,end],求取它的最右区间的下标\n",
    "        #每个区间的start不同\n",
    "        #可以对start进行排序\n",
    "\n",
    "        n = len(intervals)\n",
    "        res = [-1] * n\n",
    "        nums = [(a,i) for i,(a,b) in enumerate(intervals)]\n",
    "        nums.sort(key = lambda x : x[0])\n",
    "        print(nums)\n",
    "        for i,[a,b] in enumerate(intervals):\n",
    "            j = bisect.bisect_left(nums,(b,))\n",
    "            if j == n:\n",
    "                continue\n",
    "            res[i] = nums[j][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n=len(intervals)\n",
    "        g={}\n",
    "        for i in range(n):\n",
    "            g[intervals[i][0]]=i\n",
    "\n",
    "        intervals.sort(key=lambda x:(x[0],x[1]))\n",
    "        l1=[-1 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if intervals[i][0]==intervals[i][1]:l1[g[intervals[i][0]]]=g[intervals[i][0]]\n",
    "            else:\n",
    "                if intervals[i][1] == intervals[-1][0]:l1[g[intervals[i][0]]]=g[intervals[-1][0]]\n",
    "                elif intervals[i][1]<intervals[-1][0]:\n",
    "                    for j in range(i+1,n):\n",
    "                        if intervals[j][0]>=intervals[i][1]:\n",
    "                            l1[g[intervals[i][0]]]=g[intervals[j][0]]\n",
    "                            break\n",
    "        return l1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # Create a map to track the original index of the intervals\n",
    "        map = {interval[0]: idx for idx, interval in enumerate(intervals)}\n",
    "        \n",
    "        # Extract starting points and sort them\n",
    "        starts = [interval[0] for interval in intervals]\n",
    "        sorted_starts = sorted(starts)\n",
    "        \n",
    "        def search(target):\n",
    "            l = 0\n",
    "            r = len(sorted_starts) - 1\n",
    "            while l <= r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if sorted_starts[mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "\n",
    "            # If l is out of bounds, no interval found.\n",
    "            if l == len(sorted_starts):\n",
    "                return -1\n",
    "            return map[sorted_starts[l]]\n",
    "            \n",
    "        return [search(interval[1]) for interval in intervals]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        lefts = sorted([\n",
    "            (left, i)\n",
    "            for i, (left, right) in enumerate(intervals)\n",
    "        ])\n",
    "\n",
    "        print(f\"{lefts=}\")\n",
    "\n",
    "        ret = []\n",
    "        for _, right in intervals:\n",
    "            low, high = 0, n\n",
    "            while high - low > 1:\n",
    "                mid = (low + high) // 2\n",
    "                if lefts[mid][0] >= right:\n",
    "                    high = mid\n",
    "                else:\n",
    "                    low = mid\n",
    "            if lefts[low][0] == right:\n",
    "                ret.append(lefts[low][1])\n",
    "            elif high >= n:\n",
    "                ret.append(-1)\n",
    "            else:\n",
    "                ret.append(lefts[high][1])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divsearch(self, nums, target):\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left<=right:\n",
    "            mid = (right-left)//2+left\n",
    "            if nums[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif nums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                return mid\n",
    "        return left\n",
    "\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # hash记录\n",
    "        l = len(intervals)\n",
    "        bg, ed = [], []\n",
    "        for begin, end in intervals:\n",
    "            bg.append(begin)\n",
    "            ed.append(end)\n",
    "        pos = {}\n",
    "        for num, i in enumerate(bg):\n",
    "            pos[i] = num\n",
    "        \n",
    "        res = [] \n",
    "        bg.sort()\n",
    "        print(bg)\n",
    "        print(ed)\n",
    "\n",
    "        for i in ed:\n",
    "            print(i)\n",
    "            tmp = self.divsearch(bg, i)\n",
    "            if tmp == l:\n",
    "                res.append(-1)\n",
    "                # print(tmp, -1)\n",
    "            else:\n",
    "                res.append(pos[bg[tmp]])\n",
    "                \n",
    "                # print(tmp, bg[tmp], pos[bg[tmp]])\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        def binarysearch(nums, target):\n",
    "            n = len(nums)\n",
    "            left = 0\n",
    "            right = n - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                if target < nums[mid]:\n",
    "                    right = mid - 1\n",
    "                elif target > nums[mid]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    return target\n",
    "            if left >= n: return float(\"inf\")\n",
    "            return nums[left]\n",
    "        d = {}\n",
    "        first = []\n",
    "        for i, interval in enumerate(intervals):\n",
    "            d[interval[0]] = i\n",
    "            first.append(interval[0])\n",
    "        first.sort()\n",
    "        n = len(first)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        ans = []\n",
    "        #print(first)\n",
    "        for i in intervals:\n",
    "            target = i[1]\n",
    "            t = binarysearch(first, target)\n",
    "            if t == float(\"inf\") :\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                ans.append(d[t])\n",
    "        return ans\n",
    "        #d2 = dict(sorted(d.items()))\n",
    "        #print(d2)\n",
    "        #print(d.values)\n",
    "        #n = len(intervals)\n",
    "        #ans = [-1] * n\n",
    "        #for interval in intervals:\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        \n",
    "        n = len(intervals)\n",
    "        res = [-1] * n\n",
    "        for _, end, idx in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                res[idx] = intervals[i][2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # if len(intervals) == 1:\n",
    "        #     return [-1]\n",
    "\n",
    "        res = [-1 for _ in range(len(intervals))]\n",
    "        memo_dict = {}\n",
    "        for idx, i in enumerate(intervals):\n",
    "            memo_dict[i[0]] = idx\n",
    "            \n",
    "        search_list = [i[0] for i in intervals]\n",
    "        search_list = sorted(search_list)\n",
    "\n",
    "        def search(index, end):\n",
    "            left = 0\n",
    "            right = len(search_list) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left)//2\n",
    "                if search_list[mid] == end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    break\n",
    "                elif search_list[mid] > end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "        \n",
    "\n",
    "        for index, i in enumerate(intervals):\n",
    "            search(index, i[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        ss = {}\n",
    "        bb = []\n",
    "        qq = []\n",
    "        hh = len(intervals)\n",
    "        for i in range(hh):\n",
    "            bb.append(intervals[i][0])\n",
    "            ss[intervals[i][0]] = i\n",
    "        bbb = sorted(bb)\n",
    "        for j in intervals:\n",
    "            ttt = sorted(bbb + [j[1]])\n",
    "            h0 = ttt.index(j[1])\n",
    "            if h0 >= hh:\n",
    "                qq.append(-1)\n",
    "            else:\n",
    "                qq.append(ss[ttt[h0 + 1]])\n",
    "        return qq\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        idx = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            idx[tuple(intervals[i])] = i\n",
    "        #print(idx)\n",
    "        intervals.sort()\n",
    "        print(intervals)\n",
    "        ans=[0]*n\n",
    "        for i in range(n-1):\n",
    "            if intervals[i][0] == intervals[i][1]:\n",
    "                ans[idx[tuple(intervals[i])]] = (idx[tuple(intervals[i])])\n",
    "                continue\n",
    "            left,right = i+1,n-1\n",
    "            while left<=right and right>=i+1 and left<n:\n",
    "                middle = (right+left)//2\n",
    "                if intervals[middle][0]<intervals[i][1]:\n",
    "                    left = middle + 1\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            if left == n:\n",
    "                ans[idx[tuple(intervals[i])]] = -1\n",
    "                continue\n",
    "            ans[idx[tuple(intervals[i])]] = (idx[tuple(intervals[left])])\n",
    "        ans[idx[tuple(intervals[-1])]] = -1\n",
    "        if intervals[-1][0] == intervals[-1][1]:\n",
    "                ans[idx[tuple(intervals[-1])]] = (idx[tuple(intervals[-1])])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, p in enumerate(intervals):\n",
    "            p.append(i)\n",
    "        intervals.sort()\n",
    "\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for s, e, i in intervals:\n",
    "            j = bisect_left(intervals, [e])\n",
    "            if (j < n):\n",
    "                ans[i] = intervals[j][2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        path = [-1]*n\n",
    "        dic = {}\n",
    "        sor = []\n",
    "        for i,v in enumerate(intervals):\n",
    "            dic[v[0]] = i\n",
    "            sor.append(v[0])\n",
    "        sor = sorted(sor)\n",
    "        if n ==1 and intervals[0][0] ==intervals[0][1]:\n",
    "            return [0]\n",
    "        for j in range(n):\n",
    "            if sor[-1]>intervals[j][1]:\n",
    "                if intervals[j][1] in sor:\n",
    "                    path[j] = dic[intervals[j][1]]\n",
    "                    continue\n",
    "            if sor[-1]>=intervals[j][1]:\n",
    "                for k in range(n):\n",
    "                    if sor[k]==intervals[j][1]:\n",
    "                        if dic[sor[k]] !=j:\n",
    "                            path[j]=dic[sor[k]]\n",
    "                            break\n",
    "                    if sor[k]>intervals[j][1]:\n",
    "                        path[j]=dic[sor[k]]\n",
    "                        break                    \n",
    "        print(sor)\n",
    "        print(dic)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "\n",
    "        n = len(intervals)\n",
    "\n",
    "        ans = [-1] * n\n",
    "\n",
    "        for _, end, id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n :\n",
    "                ans[id] = intervals[i][2]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, inter in enumerate(intervals):\n",
    "            inter.append(i)\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for _, end, index in intervals:\n",
    "            pos = bisect_left(intervals,[end])        \n",
    "            if pos < n:\n",
    "                ans[index] = intervals[pos][2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        starts, ends = list(zip(*intervals))\n",
    "        starts = sorted([(start, index) for index, start in enumerate(starts)])\n",
    "        ends = sorted([(end, index) for index, end in enumerate(ends)])\n",
    "\n",
    "        ans: list[int] = [-1 for _ in range(n)]\n",
    "        i = 0\n",
    "        for end in ends:\n",
    "            while i < n and starts[i][0] < end[0]:\n",
    "                i += 1\n",
    "            if i < n and starts[i][0] >= end[0]:\n",
    "                ans[end[1]] = starts[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        # if len(intervals) == 1:\n",
    "        #     return [-1]\n",
    "\n",
    "        res = [-1 for _ in range(len(intervals))]\n",
    "        memo_dict = {}\n",
    "        for idx, i in enumerate(intervals):\n",
    "            memo_dict[i[0]] = idx\n",
    "            \n",
    "        search_list = [i[0] for i in intervals]\n",
    "        search_list = sorted(search_list)\n",
    "        print(search_list)\n",
    "\n",
    "        def search(index, end):\n",
    "            left = 0\n",
    "            right = len(search_list) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left)//2\n",
    "                if search_list[mid] == end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    break\n",
    "                elif search_list[mid] > end:\n",
    "                    res[index] = memo_dict[search_list[mid]]\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "        \n",
    "\n",
    "        for index, i in enumerate(intervals):\n",
    "            search(index, i[1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for _, end, id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                ans[id] = intervals[i][2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                if nums[mid][0] >= target: j = mid\n",
    "                else: i = mid + 1\n",
    "            for k in range(i, j+1):\n",
    "                if nums[k][0] >= target:\n",
    "                    return nums[k][-1]\n",
    "            return -1\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        \n",
    "        n = len(intervals)\n",
    "        res = [-1] * n\n",
    "        for i, (start, end, index) in enumerate(intervals):\n",
    "            pos = binarySearch(i, n-1, end, intervals)\n",
    "            res[index] = pos\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for _, end, id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                ans[id] = intervals[i][2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        m=len(intervals)\n",
    "        res=[-1]*m\n",
    "        for i in range(m):\n",
    "            start=intervals[i][0]\n",
    "            end=intervals[i][1]\n",
    "            index=self.search(intervals, i, m-1, end)\n",
    "            res[intervals[i][2]]=intervals[index][2] if 0<=index<m else -1\n",
    "        return res\n",
    "\n",
    "    def search(self, intervals, left, right, targrt):\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if intervals[mid][0]<targrt:\n",
    "                left=mid+1\n",
    "            elif intervals[mid][0]==targrt:\n",
    "                return mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right+1 if right<len(intervals) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        m=len(intervals)\n",
    "        res=[-1]*m\n",
    "        for i in range(m):\n",
    "            start=intervals[i][0]\n",
    "            end=intervals[i][1]\n",
    "            index=self.search(intervals, i, m-1, end)\n",
    "            res[intervals[i][2]]=intervals[index][2] if 0<=index<m else -1\n",
    "        return res\n",
    "\n",
    "    def search(self, intervals, left, right, targrt):\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if intervals[mid][0]<targrt:\n",
    "                left=mid+1\n",
    "            elif intervals[mid][0]==targrt:\n",
    "                return mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right+1 if right<left else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for _, end, id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                ans[id] = intervals[i][2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: list[list[int]]) -> list[int]:\n",
    "        n = len(intervals)\n",
    "        startSorted,endSorted = sorted([[intervals[i][0],i] for i in range(0,n)]),sorted([[intervals[i][1],i] for i in range(0,n)])\n",
    "        result = [0]*n\n",
    "        index = 0\n",
    "        for ele in endSorted:\n",
    "            while index<n and ele[0]>startSorted[index][0]:\n",
    "                index+=1\n",
    "            if index==n:\n",
    "                result[ele[1]] = -1\n",
    "            else:\n",
    "                result[ele[1]]=startSorted[index][1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        nums=sorted(intervals, key=lambda x: x[0])\n",
    "        res=[]\n",
    "        lg=len(nums)\n",
    "        if lg==1:\n",
    "            if intervals[0][0]==intervals[0][1]:\n",
    "                return [0]\n",
    "            else:\n",
    "                return [-1]\n",
    "        #print(nums)\n",
    "        for i in range(lg-1):\n",
    "            x,y=nums[i]\n",
    "            if y>nums[-1][0]:\n",
    "                res.append(None)\n",
    "                continue\n",
    "            if x==y:\n",
    "                res.append(x)\n",
    "                continue\n",
    "            l=i+1\n",
    "            r=lg-1\n",
    "            flag=0\n",
    "            while l<r:  \n",
    "                #print(\"====\",l,r)\n",
    "                m=l+(r-l)//2             \n",
    "                if nums[m][0]==y:\n",
    "                    res.append(nums[m][0])\n",
    "                    flag=1\n",
    "                    break\n",
    "                elif nums[m][0]>y:\n",
    "                    r=m\n",
    "                else:\n",
    "                    l=m+1\n",
    "\n",
    "            if flag==1:\n",
    "                continue\n",
    "            #print(i,l,r)\n",
    "            if nums[r][0]>=y:\n",
    "                res.append(nums[r][0])\n",
    "            else:\n",
    "                res.append(None)\n",
    "\n",
    "        res.append(None)\n",
    "        res_map={}\n",
    "        for i in range(lg):\n",
    "            res_map[nums[i][0]]=res[i]\n",
    "        \n",
    "        key_map={}\n",
    "        for i in range(lg):\n",
    "            key_map[intervals[i][0]]=i\n",
    "        tmp=[]\n",
    "        for i in range(lg):\n",
    "            if res_map[intervals[i][0]]==None:\n",
    "                tmp.append(-1)\n",
    "            else:\n",
    "                tmp.append(key_map[res_map[intervals[i][0]]])\n",
    "\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        length = len(intervals)\n",
    "        for key, value in enumerate(intervals):\n",
    "            value.append(key)\n",
    "        intervals.sort(key=lambda x: x[0])\n",
    "        result = [-1 for _ in range(length)]\n",
    "        for key, interval in enumerate(intervals):\n",
    "            if interval[0] == interval[1]:\n",
    "                result[interval[2]] = key\n",
    "                continue\n",
    "            pointer1, pointer2 = key, length - 1\n",
    "            if intervals[pointer2][0] < interval[1]:\n",
    "                continue\n",
    "            while pointer1 < pointer2:\n",
    "                center = (pointer1 + pointer2) // 2\n",
    "                if intervals[center][0] < interval[1]:\n",
    "                    pointer1 = center + 1\n",
    "                else:\n",
    "                    pointer2 = center\n",
    "            if pointer2 != key:\n",
    "                result[interval[2]] = intervals[pointer2][2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        import bisect\n",
    "\n",
    "        for index, interval in enumerate(intervals):\n",
    "            interval.append(index)\n",
    "        sorted_intervals = sorted(intervals)\n",
    "        ans = [-1] * len(sorted_intervals)\n",
    "        for _, end, index in sorted_intervals:\n",
    "            n = bisect.bisect_left(sorted_intervals, [end])\n",
    "            if n < len(sorted_intervals):\n",
    "                ans[index] = sorted_intervals[n][2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "\n",
    "        n = len(intervals)\n",
    "        ans = [-1] * n\n",
    "        for _, end, id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                ans[id] = intervals[i][2]\n",
    "        return ans\n",
    "        # res = []\n",
    "        # if len(intervals) == 1:return [-1]\n",
    "        # for i in intervals:\n",
    "        #     for j in intervals:\n",
    "        #         while i != j:\n",
    "        #             if i[1] > j[0]:\n",
    "        #                 res.append(-1)\n",
    "        #             else:\n",
    "        #                 index = []\n",
    "        #                 zhi = []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        starts, ends = list(zip(*intervals))\n",
    "        starts = sorted(zip(starts, range(n)))\n",
    "        ends = sorted(zip(ends, range(n)))\n",
    "        print(starts,ends)\n",
    "        ans, j = [-1] * n, 0\n",
    "        for end, id in ends:\n",
    "            while j < n and starts[j][0] < end:\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                ans[id] = starts[j][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        def lt436(intervals):\n",
    "            n=len(intervals)\n",
    "            res=[-1]*n\n",
    "            if n==1 and intervals[0][0]==intervals[0][1]:return [0]\n",
    "            for i in range(n):intervals[i].append(i)\n",
    "            intervals.sort(key=lambda x:x[0])\n",
    "            for l1 in range(n-1):\n",
    "                if intervals[l1][0]==intervals[l1][1]:\n",
    "                    res[intervals[l1][2]]=intervals[l1][2]\n",
    "                    continue\n",
    "                for l2 in range(l1+1,n):\n",
    "                    if intervals[l2][0]>=intervals[l1][1]:\n",
    "                        res[intervals[l1][2]]=intervals[l2][2]\n",
    "                        break\n",
    "            return res\n",
    "        return lt436(intervals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        \n",
    "        n = len(intervals)\n",
    "        ans = [-1]* n\n",
    "        for _,end,id in intervals:\n",
    "            i = bisect_left(intervals, [end])\n",
    "            if i < n:\n",
    "                print(i)\n",
    "                ans[id] = intervals[i][2] \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        first = []\n",
    "        second = []\n",
    "        for k, i in enumerate(intervals):\n",
    "            first.append([i[0], k])\n",
    "            second.append([i[1], k])\n",
    "        first.sort()\n",
    "        second.sort()\n",
    "        n = len(intervals)\n",
    "        ans = [-1 for _ in range(n)]\n",
    "        k = 0\n",
    "        for i in second:\n",
    "            if i[0] == intervals[i[1]][0]:\n",
    "                ans[i[1]] = i[1]\n",
    "                continue\n",
    "            while k < n and (first[k][0] < i[0] or first[k][1] == i[1]):\n",
    "                k += 1\n",
    "            if k < n:\n",
    "                ans[i[1]] = first[k][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        start,end = [],[]\n",
    "        n=len(intervals)\n",
    "        ret=[-1]*n\n",
    "        for i in range(n):\n",
    "            start.append([intervals[i][0],i])\n",
    "            end.append([intervals[i][1], i])\n",
    "        start.sort()\n",
    "        end.sort()\n",
    "        startIndex=0\n",
    "        for endIndex in range(n):\n",
    "            endVal=end[endIndex][0]\n",
    "            while startIndex<n and start[startIndex][0]<endVal:\n",
    "                startIndex+=1\n",
    "            if startIndex<n:\n",
    "                ret[end[endIndex][1]]=start[startIndex][1]\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        def bisearch_left(arr, end):\n",
    "            if len(arr) == 0:\n",
    "                return -1\n",
    "            '''\n",
    "            寻找大于等于目标值的位置, 可以是自己\n",
    "            '''\n",
    "            left, right = 0, len(arr) - 1\n",
    "            while left < right:\n",
    "                mid = left + ((right-left) >> 1)\n",
    "                # print(left, right, mid)\n",
    "\n",
    "                # 如果目标值大于中间值，则左移\n",
    "                if end > arr[mid][0]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    # 如果目标值小于等于中间值：\n",
    "                    right = mid \n",
    "            return arr[right][2] if arr[right][0] >= end else -1\n",
    "        \n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        # 按照区间开始进行排序\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        ans = [-1]*n\n",
    "        for t, (_,  end , id) in enumerate(intervals[:-1]):\n",
    "            # print(t, intervals[t:],end)\n",
    "            ans[id] = bisearch_left(intervals[t:], end)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        #找一个区间j，startj >= endi\n",
    "        l = len(intervals)\n",
    "        res = []\n",
    "        for i in range(l):\n",
    "            intervals[i].append(i)\n",
    "        intervals2 = intervals.copy()\n",
    "        intervals2.sort(key = (lambda x:x[0]))\n",
    "\n",
    "        Dict = dict()\n",
    "\n",
    "        def mybinary(nums,item):\n",
    "            left = 0\n",
    "            right = len(nums)-1\n",
    "            mid = left + (right - left)//2\n",
    "            while left<right:\n",
    "                \n",
    "                if nums[mid][0] > item:\n",
    "                    right = mid\n",
    "                elif nums[mid][0] < item:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    break\n",
    "                mid = left + (right - left)//2\n",
    "            return nums[mid][-1]\n",
    "        for i in intervals:\n",
    "            if i[1] in Dict:\n",
    "                res.append(Dict[i[1]])\n",
    "                continue\n",
    "            else:\n",
    "                if i[1] > intervals2[-1][0]:\n",
    "                    res.append(-1)\n",
    "                    continue\n",
    "                index = mybinary(intervals2,i[1])\n",
    "                res.append(index)\n",
    "                Dict[i[1]] = index\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i in range(len(intervals)):\n",
    "            intervals[i].append(i)\n",
    "        intervals.sort()\n",
    "        ans = []\n",
    "        search = [n[0] for n in intervals]\n",
    "        for i in range(len(intervals)):\n",
    "            p = bisect.bisect_left(search , intervals[i][1])\n",
    "            if p == len(intervals):\n",
    "\n",
    "                ans.append([intervals[i][2], -1])\n",
    "            else:\n",
    "                ans.append([intervals[i][2],intervals[p][2]])\n",
    "        ans.sort()\n",
    "        return [x[1] for x in ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # 二分查找第一个满足条件的目标\n",
    "        def findRightIndex(curInterval:List[int]) -> int:\n",
    "            n = len(sortedIntervals)\n",
    "            s = 0\n",
    "            e = n - 1\n",
    "            while s <= e:\n",
    "                m = (e - s) // 2 + s\n",
    "                t = sortedIntervals[m]\n",
    "                if curInterval[1] == t[0]:\n",
    "                    return t[2]\n",
    "                elif curInterval[1] < t[0]:\n",
    "                    if m > 0 and curInterval[1] <= sortedIntervals[m - 1][0]:\n",
    "                        e = m - 1\n",
    "                    else:\n",
    "                        return t[2]\n",
    "                elif curInterval[1] > t[0] :\n",
    "                    if m < n - 1 :\n",
    "                        if curInterval[1] > sortedIntervals[m + 1][0]:\n",
    "                            s = m + 1\n",
    "                        else:\n",
    "                            return sortedIntervals[m + 1][2]\n",
    "                    else:\n",
    "                        return -1\n",
    "\n",
    "        # 构造带位置的元组列表\n",
    "        for i in range(len(intervals)):\n",
    "            intervals[i].append(i)\n",
    "        \n",
    "        # 根据起点排序\n",
    "        sortedIntervals = sorted(intervals , key=lambda interval:interval[0])\n",
    "\n",
    "        result = []\n",
    "        for interval in intervals:\n",
    "            result.append(findRightIndex(interval))\n",
    "        \n",
    "        return result\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "\n",
    "        its = [[i, 1, s] for i, [s, e] in enumerate(intervals)]\n",
    "        its += [[i, 0, e] for i, [s, e] in enumerate(intervals)]\n",
    "        its = sorted(its, key=lambda x:(x[-1], x[-2]))\n",
    "\n",
    "        # print(its)\n",
    "        res = [-1] * len(intervals)\n",
    "        queue = []\n",
    "        for [index, tag, se] in its:\n",
    "            if tag == 0:\n",
    "                queue.append([index, se])\n",
    "            else:\n",
    "                while len(queue)>0 and se >= queue[0][-1]:\n",
    "                    i = queue[0][0]\n",
    "                    res[i] = index\n",
    "                    queue = queue[1:]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        for i, interval in enumerate(intervals):\n",
    "            interval.append(i)\n",
    "        intervals.sort()\n",
    "        n = len(intervals)\n",
    "        print(intervals)\n",
    "        # ans = [-1]*n\n",
    "        res = [-1]*n\n",
    "        for now,interval in enumerate(intervals):\n",
    "            _,end,id = interval\n",
    "            # i = bisect_left(intervals,[end]) #二分查找库函数\n",
    "            l,r = now,n-1\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                print(l,r,mid)\n",
    "                if intervals[mid][0] < end:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid-1\n",
    "            if l<n:\n",
    "                res[id] = intervals[l][2]\n",
    "            # if i<n: #存在intervals>=end\n",
    "            #     ans[id] = intervals[i][2]\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:\n",
    "        n = len(intervals)\n",
    "        for i in range(n):\n",
    "            intervals[i].append(i)\n",
    "        clone = sorted(intervals)\n",
    "        res=[0 for _ in range(n)]\n",
    "        print(clone)\n",
    "        for i in range(n):\n",
    "            left,right = 0,n-1\n",
    "            need = intervals[i][1]\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                # if clone[mid][0]==need: \n",
    "                #     res[i] = clone[mid][2]\n",
    "                #     break \n",
    "                if clone[mid][0]>=need:\n",
    "                    right=mid-1\n",
    "                else:\n",
    "                    left=mid+1\n",
    "            if left==n: res[i] = -1\n",
    "            else: res[i] = clone[left][2]\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
